// 查找总价格为目标值的两个商品
class Solution 
{
public:
    vector<int> twoSum(vector<int>& price, int target) 
    {
        // 1、数据初始化
        int left = 0, right = price.size() - 1;
        // 2、利用双指针解决问题
        while(left < right)
        {
            int sum = price[left] + price[right];
            if(sum < target) ++left;
            else if(sum > target) --right;
            else return {price[left], price[right]};
        }
        // 题目没有明确说明没有结果的话会怎么样，那么该题的测试用例应该都是有结果的
        // 为了照顾编译器要求一定要返回一个结果，所以我们最后返回一个空数组即可
        return {};
    }
};
/*
- 时间复杂度：O(n)
- 空间复杂度：O(1)
*/

// 有效三角形的个数
class Solution 
{
public:
    int triangleNumber(vector<int>& nums) 
    {
        // 1、优化
        sort(nums.begin(), nums.end());
        // 2、利用双指针解决问题
        int ret = 0, n = nums.size();
        for(int i = n - 1; i >= 2; --i)
        {
            int left = 0, right = i - 1;
            while(left < right)
            {
                // 当 a+b>c ，a下标属于 [left, right-1]时，都能和 b、c 构成三角形
                // 当 a+b<=c ，b下标属于[left-1, right]时，都不能和 a、c 构成三角形
                if(nums[left] + nums[right] > nums[i])
                {
                    ret += right - left;
                    --right;
                }
                else ++left;
            }
        }
        // 返回值
        return ret;
    }
};

/*
- 时间复杂度：O(n^2)
- 空间复杂度：O(1)
*/

// 盛最多水的容器
class Solution 
{
public:
    int maxArea(vector<int>& height) 
    {
        int left = 0, right = height.size() - 1;
        int ret = INT_MIN;
        while(left != right)
        {
            // 容积 = 长度 * 高度
            int v = (right - left) * min(height[left], height[right]);
            ret = max(ret, v);
            // 移动指针 - 谁小移动谁
            height[left] < height[right] ? ++left : --right;
        }
        return ret;
    }
};
/*
- 时间复杂度：O(n)
- 空间复杂度：O(1)
*/
